from collections import deque

def bfs(graph, start, goal):
    # 记录已经访问过的节点
    visited = set()
    # 使用队列来存储待访问的节点，以及到达该节点的路径
    queue = deque([(start, [start])])
    print("quque:", queue)

    while queue:
        # 取出队列中的第一个元素
        (vertex, path) = queue.popleft()
        print("(vertex, path):", (vertex, path))
        # 如果当前节点是目标节点，则返回到达该节点的路径
        if vertex == goal:
            return path

        print("set(path):", set(path))

        for next in graph[vertex] -set(path):
            print("next:", next)
            if next not in visited:
                visited.add(next)
                queue.append((next, path + [next]))

    return None

if __name__ == '__main__':

    # 示例：定义一个简单的图
    graph = {
        'A': set(['B', 'C']),
        'B': set(['A', 'D', 'E']),
        'C': set(['A', 'F']),
        'D': set(['B']),
        'E': set(['B', 'F']),
        'F': set(['C', 'E'])
    }

    # 调用 bfs 函数，从节点'A'开始搜索到节点'F'
    print("bfs_result:", bfs(graph, 'A', 'F'))  # 输出: ['A', 'C', 'F']